/**
 * Created with IntelliJ IDEA.
 * Description: leetcode: 123. 买卖股票的最佳时机 III
 * <a href="https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/">...</a>
 * User: DELL
 * Date: 2023-09-01
 * Time: 22:56
 */
public class Solution {
    /**
     * 解题思路: (动态规划)
     * 本题的主要难点在于剖析两次彩票的买入和卖出会将人的状态分为以下五种:
     * 1. 未进行过任何操作；
     * 2. 只进行过一次买操作；
     * 3. 进行了一次买操作和一次卖操作，即完成了一笔交易；
     * 4. 在完成了一笔交易的前提下，进行了第二次买操作；
     * 5. 完成了全部两笔交易。
     * 之后需要对这五种状态分别进行状态转移分析.
     * 状态定义: buy1 和 buy2 分别表示状态 2 和状态 4
     *         sell1 和 sell2 分别表示状态 3 和状态 5
     * 状态转移: buy1 = max{buy1,-prices[i]}
     *         sell1 = max{sell1,buy1+prices[i]}
     *         buy2 = max{buy2,sell1-prices[i]}
     *         sell2 = max{sell2,buy2+prices[i]}
     * 初始化: buy1 = -prices[0] , buy2 = -prices[0]
     *        sell1 = 0 , sell2 = 0
     * 返回值: sell2
     *
     * 以上状态定义转移初始化和返回值再leetcode题解中讲解的很清楚,链接如下:
     * <a href="https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/solutions/552695/mai-mai-gu-piao-de-zui-jia-shi-ji-iii-by-wrnt/">...</a>
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        // 合法性检验
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int buy1 = -prices[0];
        int buy2 = -prices[0];
        int sell1 = 0;
        int sell2 = 0;
        for (int i = 1; i < prices.length; i++) {
            buy1 = Math.max(buy1,-prices[i]);
            sell1 = Math.max(sell1,buy1+prices[i]);
            buy2 = Math.max(buy2,sell1-prices[i]);
            sell2 = Math.max(sell2,buy2+prices[i]);
        }
        return sell2;
    }
}